1. Field of the Invention
This invention relates to extensible mark-up language (XML) and more particularly relates to XML query evaluation using early-outs and multiple passes.
2. Description of the Related Art
XPath and XQuery are two common languages used to query an XML document. XPath is a path expression language for selecting data within XML documents. XQuery is a language for querying, transforming, and constructing XML data. An expression is a string of unicode characters which may be constructed from keywords, symbols, and operands. XPath allows expressions to be nested. XQuery uses XPath expression syntax to address specific parts of an XML document and is semantically similar to structured query language (SQL). The SQL-like XQuery syntax uses “For,” “Like,” “Where,” “Order by,” and “Return” clauses in a “FLWOR” expression.
XPath analyzes an XML document as an XML tree by representing each element of the XML document as a node in the XML tree. The XML tree may include parent-child nodes that directly correspond to the nested elements in the XML document. For more information regarding XPath and XQuery please visit the proposed recommendations of W3C which currently reside at http://www.w3.org/TR/x/path20/ and http://www.w3.org/TR/xquery/ respectively.
A query, whether written using XPath or XQuery, is typically executed following a single-pass evaluation procedure, also referred to as a streamlined evaluation procedure. Using a single-pass evaluation procedure, all of the steps of the query are sequentially evaluated to gather all of the data in a single pass and thereby prevent re-traversals (i.e., subsequent traversals) through the XML document. However, certain queries may not need every step evaluated in order to qualify the XML document. The XML document is qualified when it meets the search criteria of the query.
One example is logical expressions such as an “AND” expression or an “OR” expression. For example, when one step or component of an “AND” expression is found to be false, the entire “AND” expression is false. Furthermore, when one step or component of an “OR” expression is found to be true, the entire “OR” expression is true. In these cases, query evaluation can exit early and avoid needlessly evaluating every step in the query. Similarly, a logical expression may include an XQuery “FLWOR” expression wherein the “For” clause contains an implied conjunction. As with typical “And” expressions, the implied conjunction is false if one component is false.
From the foregoing discussion, Applicants assert that a need exists for a method and apparatus that more efficiently evaluates XML queries. Beneficially, such a method and apparatus would selectively use a multi-pass evaluation procedure to evaluate XML documents.